Given the growing complexity of modern software systems, there is an increasing demand for easier ways of locating errors and for ensuring or verifying the correctness of software designs. Tools for accomplishing these purposes range from the simple type checking provided by many compilers and source code analysis tools to formal verification proofs.
The former, unfortunately, miss many common errors. The latter involve constructing rigorous mathematical proofs. Such proofs are extremely difficult to construct with automation research limited to small programs. Despite limited successes, these solutions do not scale to non-trivial software. Consequently, formal verification is rarely used in practice. Jackson (see U.S. Pat. No. 5,423,027) has proposed a compromise solution. This approach does not eliminate errors as does formal verification, but it lends itself to automation and does catch more errors than simple type checking (during compilation). This is accomplished via optional programmer input and an automated checking tool that references various aspects (e.g., properties) of objects (types) rather than variables. The invention involves (a) specifying input and output values of these aspects for each procedure in a program, (b) examining and constructing an approximation of actual dependencies in procedural code and (c) comparing the approximate dependencies with the procedural specifications. The comparison of specifications with the approximations in the procedural code is used to identify omissions in the latter.
The above approach, in effect, is concerned with better ways to check given source code. The Jackson invention does not deal with design issues, cannot guarantee correctness and any concrete realization must address language specific issues.
Gaboury (U.S. Pat. No. 5,481,717) takes a different approach to formal verification. In parallel with our own efforts, Gaboury has disclosed a method for verifying a computer program in relation to its specification. This method is an extension of an existing Binary Decision Diagram algorithm to compare Finite State Machines, and involves comparison of a program and its specification after they both have been represented as logic programs (e.g., in Prolog, using variables and production rules). The basic method disclosed by Gaboury involves: (a) converting two logic programs into corresponding finite state machines, each having internal states, input values and output values, (b) determining the data types of the variables of the logic programs, (c) converting all expressions in the logic program into disjunctive form, (d) expanding procedure calls into procedure bodies, (e) translating the programs into transition functions and (f) determining whether equivalencies between internal states, input values and output values of the two finite state machine descriptions produce equivalent output values for all equivalent input values and states.
As with the Jackson method, however, this method requires formal verification of both specifications and solutions as parameterized logic programs. This method offers one way to solve the problem of unspecified parameters (e.g., in specifications); it effectively replaces details with unspecified parameters for comparison purposes. Although this approach is theoretically plausible, it solves the problem by introducing non-intuitive elements into the specification. By way of contrast, the present disclosure has no requirement that either the specification or the program be represented as a logic program. Specifications deal exclusively with input-output behavior and implementations are represented in traditional (sequential/event driven) real world terms.
In a similar vein the Gaboury disclosure eliminates syntactic differences such as variable names. Syntactic differences involving names, for example, although of limited importance in mathematical formulations, play an important role in human understanding. They are essential in building and maintaining complex, real world software. In effect, the Gaboury approach is not likely to be very helpful either during development or during ongoing maintenance. Moreover, the method cannot be used with many kinds of software because comparison of unrestricted logic programs is an undecidable problem.
Rather than verifying correctness after implementation, other approaches attempt to improve software quality by design. One approach derives from contemporary software and system development methodologies (e.g., structured analysis [Hatley & Pirbhai, 1987; Yourdon, 1989]; information engineering [Chen, 1976; Flaatten et al, 1989], object oriented design [Booch, 1994; Rumbaugh et al., 1991]). Most of these methods make a sharp distinction between design, implementation and testing. Implementation, for example, comes after design, and although limited consistency checking is included in many CASE tools, correctness testing is postponed until after implementation. Given exponential growth with complexity in the number of paths to be tested, these methodologies make complete verification testing impossible. For example, after implementation, a simple system having a sequence of 100 binary decisions has 2.sup.100 independent paths to be tested. Clearly, it is impossible to fully verify the correctness of even moderate sized programs empirically. However, only 300 paths are involved if testing is done at successive levels of refinement (see Scandura, 1992, p. 92). In this case the number of paths goes up only additively.
Traditional approaches to proving that software is correct (i.e., does exactly what specifications call for) require proving that the program will produce the desired output for any given set of inputs. This is true whether one attempts to prove correctness after software has been developed (e.g., Hoare & Shepherdson, 1985) or at successive stages of process refinement as in clean room engineering (Linger, 1994) and higher order software (Martin, 1985).
In contrast to the above, clean room engineering is based on mathematically rigorous correctness methods and has been successfully applied in a number of projects. The approach, however, involves manual verification (e.g., Linger, 1994; Linger, Mills & Witt, 1979). It is based on a hardware metaphor (where one knows all inputs and outputs before designing a system) and has not been shown to scale well to larger software systems. In recognition of the complexities of verification during development, "clean room" puts a heavy emphasis on software testing after implementation based on statistical sampling methods. Martin (1985) describes an alternative approach developed by Hamilton and Zeldin that is based on provably correct design constructs. The latter, however, also requires formal, non-intuitive modeling techniques, which again are not easily applied to large systems. A fundamental limitation of these methods is they assume that all input and output variables to a proposed system have been specified prior to system analysis (e.g., Martin, 1985, p. 50). This complicates design, especially in larger systems. Furthermore, no provision is made in the Martin (1985) approach for formulating precise specifications. Even where this is done, proving correctness is impractical using these methods because the numbers of input-output relationships to be verified is simply too large.
In contrast with Jackson, this invention deals with software design as well as code. Like other software engineering methodologies, its goal is to make software easier to understand, construct and modify. Unlike software engineering methodologies, however, including the more complete consistency checking provided by cleanroom engineering and Hamilton's "provably correct designs", the method proposed herein not only ensures consistency but it guarantees that software is correct by design and lends itself to automation.
Rather than catching errors after implementation, like Jackson, the latter more promising approaches attempt to ensure correctness by design. Cleanroom engineering, for example, has been successfully applied in a number of projects, but to date the approach involves manual verification (e.g., Linger, 1994; Linger, Mills & Witt, 1979). The "correctness theorem" (e.g., Linger, Mills & Witt, 1979, p. 222) shows that proving that a sequence refinement is correct involves direct comparison with the parent's behavior; a selection refinement involves checking at least two (branching) conditions; iteration requires checking three conditions, the third involving loop termination. This theorem simply states what must be shown to prove correctness--it refers essentially to syntactic consistency of a refinement. We refer to a refinement, which syntactically distinguishes these conditions, as "internally consistent". Actually demonstrating the correctness of any such condition with respect to its specification requires formal proof.
Martin (1985) describes an alternative approach to internal consistency developed by Hamilton and Zeldin. Although variously referred to as "provably correct" or higher order software, this approach involves showing designs to be consistent in the sense that each type of refinement follows certain specified rules. For example, a sequence refinement is consistent if and only if the input of the first sequence element is the same as the input to the parent, the output of the last sequence element is identical to the output of the parent and the output of each successive sequence element serves as input to the next element in the sequence. This approach requires the designer to adopt an entirely different mind set. Rather than using sequence, selection and iteration refinements, for example, the designer must adopt refinement types that are unfamiliar, and less easily applied to large systems. Even more basic, the approach does not address the issue of correctness with respect to independently defined specifications.
Although proving consistency in clean room engineering and in higher order software appears to be relatively straightforward (e.g., Linger, Mills & Witt, 1979; Martin, 1985), ensuring consistency in practice has been difficult because all input and output variables must be specified prior to system analysis. Except possibly in well organized data base applications, it is impossible even in relatively small systems, to know all possible input and output variables before a system has been implemented. Even here, checking for internal consistency gets increasingly cumbersome as systems get increasingly complex. Indeed, practically speaking, it would be impossible to achieve this goal with the large, complex systems on which government, industry and increasingly the home user depend.
Although processes are refined hierarchically, this is not the case with data. Both clean room and higher order software are based on a hardware metaphor where it is assumed that all inputs and outputs are known from the beginning (of design). In order to design a chip, for example, one must first know all of the input and output pins.
Apart from the hardware metaphor, reliance on a priori specification of all input and output variables derives from the tendency of most software engineers to think about software in terms of code. While the number of inputs and outputs to be considered at each stage of analysis can be reduced via top-down analysis, existing software engineering technologies (e.g., Chen, 1976) deal with data independently of process. There is no relationship between the abstraction levels in data and those in the corresponding design. Although contemporary object-oriented approaches (Booch, 1994; Rumbaugh et al, 1991) allow both data and process abstraction, processes are syntactically grouped according to data. Real world modeling, however, frequently and naturally calls for grouping data (structures) by semantically equivalent processes defined on such data. Furthermore, none of the above methods comes close to ensuring logical consistency of actual software.
In order to ensure such consistency, the numbers of variables to be considered during the design and implementation processes becomes unwieldy. Consequently, neither clean room engineering nor higher order software has been shown to scale well to larger software systems. In a recent talk, Sherer (1994), for example, has admitted a practical limit of 10,000-12,000 lines of code. To summarize, both methods assume that all inputs and outputs to a proposed system have been specified prior to system analysis.
Proving correctness with respect to external specifications is an even more daunting task. One must show that every possible sequence of input values to the system produces the correct output. Indeed, in describing higher order software, Martin (1985, p. 271-2) explicitly disavows the possibility of proving correctness with respect to external specifications. Similarly, in clean room engineering the task is viewed as being of only theoretical interest.
Proving correctness requires showing that a program produces the same behavior as designated in some independent specification. Proving correctness is impractical not only with complete systems but even where individual refinements must be shown to be consistent and correct (children with respect to their parent) during the design process. In standard approaches, the number of inputs and outputs invariably is simply too large. It is difficult in practice to keep track of the variables allowed--much less to prove that each instance of behavior is correct. In recognition of this fact, "clean room" puts a heavy emphasis on software testing after implementation based on statistical sampling methods.
To summarize these two points, internal consistency involves syntactic constraints between the parent in a refinement and its children. Ensuring internal consistency gets increasingly complex as the number of input and output variables gets larger and larger. Proving correctness of any given refinement is even more complex. This requires that refinement components produce the same results as their parent. This is impractical (if not impossible) with realistic software systems.
A third limitation of current approaches to proving correctness derives from the traditional standards used for this purpose. In order to prove that a program is correct with respect to its specification, one must begin by assuming that some basic set of functions operates correctly (e.g., the standard arithmetic functions of addition, subtraction, etc.). Typically, the same basic set is predetermined and assumed irrespective of the program or application. All proofs are effectively judged relative to a single standard. For example, consider some specified functional relationship and a program EQU d:=prog(a, b, c)
which maps each set of inputs to the function (i.e., a, b and c) into the specified response (i.e., d). In this case we must prove that the program prog produces the same behavior as the specified function.
That is, the function prog is correct if and only if prog's behavior can be produced using the basic set of assumed component functions (e.g., +, /) of which prog is composed. Notice that these component functions are assumed to operate on the same input values and/or values derived therefrom, as does prog itself. This is true at all levels of refinement in a design for prog. In each case there exists a unique output integer d.sub.i for each set of input integers a.sub.i, b.sub.i, c.sub.i, to the specification. In general, the task of proving correctness can be reduced to showing that the behavior associated with any given level in a refinement hierarchy is identical to that of the corresponding refinement, and that, ultimately, with a terminal refinement consisting entirely of the assumed basic functions. Although proving correctness of individual refinements is much simpler than proving that a (complete) design or program is correct, even the latter is a very demanding task. There is no known general-purpose solution that can accommodate arbitrarily complex components.
We have identified three basic limitations of current formal verification techniques as they are presently formulated: (1) the implicit assumption of a hardware metaphor which implies that all input and output variables must be specified prior to process refinement, (2) the assumption that the values of the variables referenced at all abstraction levels in a program design must be identical and (3) the practice of proving correctness with respect to a predetermined set of basic functions. The first limitation leads to unmanageable numbers of input and output variables in developing logically consistent designs. The second leads to the impossibility of devising any universal method for proving correctness. The third leads to impracticability with non-trivial systems. Any one of these limitations makes standard approaches impractical for use in actual practice.
In addition, current approaches have been unfamiliar and nonintuitive requiring highly specialized training. Indeed, existing formal techniques deal primarily, if not exclusively, with internal consistency. The correctness of programs cannot be assured. This requires comparing specifications (what a program is supposed to do) with what the program actually does. The sheer variety of possible inputs and outputs makes this impractical.
Cognitive Research
A completely different approach to the problem of system design derives from earlier research on human cognition and, in particular on structural (cognitive task) analysis by the present inventor. Structural analysis of a problem domain (corresponding to a specification in software engineering) requires specifying one or more "solution rules" (corresponding to language independent designs) which is sufficient for solving all problems in the domain. Each solution rule consists of a triple, domain (inputs), range (outputs) and procedure or operation. Rather than assuming (as standard software engineering approaches) that one knows all inputs and outputs at the beginning of analysis, these inputs and outputs are assumed to be known--that is, objectively specified--only to the same degree as the corresponding operation.
Structural analysis evolved over a long period of time and has been applied in the analysis of a wide variety of problem domains for both basic research on human cognition and the design of instructional materials (e.g., Scandura, 1971, 1973, 1977; Scandura, Durnin, Ehrenpreis et al, 1971; Scandura & Scandura, 1980). Most of the earlier research was directed at the identification of higher order rules--that is to identifying rules which operate on and/or generate other rules. Given a problem domain, typically one so complex that no one solution rules could reasonably be identified, this method involved first identifying subsets of the domain for which solution rules could readily be specified. Then "parallels" (i.e., analogies, similarities, etc.) among the various solution rules were used to specify higher order rules making it possible to automatically generate these and/or new solution rules (for new problem subsets) from more basic rules. Scandura (1982, 1984a) both summarizes much of this research and more fully details a method for specifying individual lower and higher order rules.
As described in Scandura (1984a), this method (which at the time was evolving completely independently of parallel work in software engineering) involved analyzing both data (problems) and solution processes in parallel from the top down. In essence, representative problems where solved step-by-step at successive levels of analysis from the top-down. Essentials of this method are best understood from the description given by Scandura (1984a).
" . . . top-down analysis has the advantage of making clear to the user the "flow of control" of the solution procedure. It also allows for arbitrary levels of procedural refinement. Top-down analysis deals with specific problem characteristics only in an informal heuristic manner . . . there is a close connection between the domain of a problem and the corresponding solution procedure. Informal awareness of either one necessarily influences specification of the other. It would be highly desirable to make such awareness public.
Step-by-step analysis, by way of contrast, deals more directly with particular problems and solution steps. It also provides a potentially mechanical means of translating sequences of solution states into general procedures. But, there are sometimes ambiguities as to overall structure and flow of control. This ambiguity derives from lack of specification of the interrelationships between problem domain and procedural representation.
. . . a method of analyzing procedures which combines the advantages of top-down and step-by-step analyses could go a long way toward providing the kind of objective and systematic method we seek.
One method is to employ problem and step-by-step analyses at progressive levels of top-down analysis. In this method the problem representation and the solution algorithm are refined in parallel. We illustrate the method in the context of subtraction, while emphasizing general principles.
I. First, the analyst would construct a column subtraction problem (on intuitive grounds). For example: ##STR1##
This problem, then, would be used to specify the corresponding problem domain to a first level of approximation. Toward this end, the analyst would employ the following procedure:
A. Identify the minimum essential characteristics of the problem which make it a problem of the desired type. Specifically, with regard to column subtraction, the "-" sign, the ".sub.------ ", the two numerals (437 and 275), where the one on top designates a number that is larger than the bottom one, constitute the "given" of the problem. The unspecified solution numeral (the one that goes under ".sub.------ ") specifies the problem goal.
B. Identify those input (i.e., "given") characteristics which may vary without changing the essential nature of the problem. By essential nature is meant those qualities of the problem which make it solvable via the, at this point, only intuitively known solution procedure associated with the problem. In the case of a column subtraction problem these characteristics are the two numerals, where the top one is greater than or equal to the bottom one.
C. Replace each such input characteristic with a variable and specify the sets of allowable values of these variables. In the case of subtraction, there are two domain variables: Top number (T), and bottom number (B), such that T&gt;B.
Carrying out Steps A, B and C yields a problem schema which formally represents the domain of the associated rule to a first approximation.
Given the rule domain, the analyst next solves the original problem as specified and uses the resulting states as a basis for specifying the solution procedure. More exactly, the analyst uses the following method.
D. Take the specified values of the input variables of the original problem as inputs and apply step by step the solution procedure, which at this point is known only intuitively. In the case of the above subtraction problem, the analyst just subtracts the two given numbers--i.e., specified the solution. In doing this, he can refer formally speaking only to the variables (numbers) as wholes. Hence, the result is just a pair of states, the subtraction problem before and the subtraction problem after the difference has been written. (The analyst cannot refer to individual digits, for example, since they do not yet exist from the standpoint of the formal analysis. They are known intuitively to the analyst, but have not yet been represented formally. Hence, the digits cannot be referred to explicitly in formally representing the solution procedure at this level.)
E. Go to the first pair of states. (In this case there is only one pair of states: the subtraction problem itself and the problem together with its solution.) Identify the atomic operation corresponding to this pair of states. In this case, let us just call it "subtract." Since these are the only states, we are finished.
F. Identify the "normal" domain of the operation(s) identified, using a variation of step C. Specifically, over what ranges of values can the initial problem state vary without affecting applicability of the atomic operation? Equivalently, what is the corresponding atomic rule? In the present case, the normal domain is just the domain of subtraction problems as specified above.
G. Identify the extra-domain condition, if any, which must be satisfied if this atomic rule (operation--plus domain and implied range) is to be applied. In the context of the intuitively known solution procedure, the "subtract" atomic rule applies to every element in its domain (i.e., to all pairs of numbers where the top one is not smaller than the bottom one). Hence, there are no extra-domain conditions.
Since there is only one atomic rule in the solution procedure, we are finished. The "subtract" atomic rule is THE required solution rule at this level. (Note: This subtract rule consists of the subtraction operation, together with the problem domain and goal.)
II. Reapplication of step-by-step analysis gives a more finely structured rule [i.e., representation] at the next level of top-down analysis. At this point, we may select any problem (including the original one) from the subtraction domain, which we have formally characterized in terms of the "-", ".sub.------ ", and two number variables. (The unspecified solution variable constitutes the range.)
The first phase in refined analysis is to repeat the above steps (A-G) at a next level of detail.
A. What additional characteristics of the problems are referred to in applying the intuitively known solution procedure? In the case of column subtraction problems, columns clearly constitute additional characteristics because solutions proceed column by column.
B/C. Representation of the domain of subtraction problems thereby is enriched by allowing for a variable number of columns (from one up).
D. Next, the given problem is solved taking columns into account. That is, the subtract atomic rule (i.e., component) is refined. It is replaced with a sequence of states of the form ##STR2##
each state having one more digit zi than the preceding state (indicating that one more column has been subtracted).
IMPORTANT: The (xi, yi) column and the (zi-1) are encircled to distinguish these ACTIVE components of the problem (at state i) from those that are inactive. Active components are those that are attended to (i.e., operated on by the associated atomic rules) at any given step (state) of a problem solution. The square surrounding "zi" denotes the goal to be achieved at state i. (Notice at the initial level of analysis that both of the two given numbers are "active" in this sense.)
E-F. Next, the transition between the first pair of states is specified by the atomic rule "Go to the first column on the right and subtract." In turn, each successive state transition is specified by the atomic rule "Go to the next column to the left and subtract." The domain of this atomic rule is a problem schema. The active components in the schema are the just determined (last) digit in the partial difference (i.e., zi), which determines what the next column to the left is, and that column, which determines the column difference. As before, the result is a sequence of atomic rules.
G. Here, we see that the first atomic rule applies to every subtraction problem. There are no "extra-domain" conditions. Each of the succeeding atomic rules, however, is applied only when there is another column to the left (otherwise the problem is finished). Consequently, we introduce the extra-domain condition "There is a next column."
Suppose now that we have applied Steps D-G to just one problem (it could be the original one). At this point, we have a sequence of atomic rules, together with extra-domain conditions immediately preceding all but the first.
Where such extra-domain conditions exist, further analysis is required.
H. Examine each of the extra-domain conditions to determine whether some succession of the following atomic rules ever generates an output state whose active components satisfy the extra-domain condition (as well as the domain of the first atomic rule following the extra-domain condition). The given problem has three columns, so there is another column after subtracting each of the first two columns.
Indeed, by choosing a suitable problem, this extra-domain condition can be satisfied any number of times. Irrespective of how many columns are chosen, there is always some problem with one more column. What this means, effectively, is that any number of applications of the atomic rule "Go to (i.e., attend to or activate) the next column and subtract the column" is possible (with some problem). Alternatively, reapplication is indicated until an output state is generated (e.g., a fully solved problem) that no longer satisfies the extra-domain condition--namely, "There is no next column." Moreover, when this extra-domain condition is no longer satisfied, the process STOPS so the underlying procedure is completely defined.
Whenever such reapplication (of some succession of atomic rules) is indicated, the extra-domain condition in question defines an iteration. Equivalently, the successive atomic rules may be replaced by a loop, given a more efficient representation of the solution procedure.
More generally, one checks first to see if an extra-domain condition defines an iteration (i.e., loop). If it does not, and only if it does not, then it necessarily defines a selection.
III. Again, one can reapply step-by-step structural analysis to components of the Level II solution rule. As in the previous more informal top-down analysis, the "Subtract the column" atomic rule is one obvious candidate.
A. In this case, close attention is paid to what is done in subtracting individual columns, again building on the analyst's informal awareness of the solution procedure. In subtracting the first column of the given problem ##STR3##
we get the partial answer (2) directly. In the next column, however, we must "borrow" in order to subtract (3-7)--where borrowing involves reference to the top digit (4) in the next column.
In effect, at this third level of analysis it is necessary to distinguish individual digits in the subtraction problem. (The digits then constitute the "additional" characteristics.)
B/C. Each of these digits, in turn, may be replaced with a variable ranging from 0 to 9 (subject to the overall constraint that the top numeral represents a larger number than that bottom one).
D. Next, we detail more fully the sequences of states associated with designated components (e.g., the subtract column atomic rule) of the previously determined solution procedure. This is accomplished by solving the above, more finely structured problem, giving explicit attention to the "additional" characteristics specified. Consider a case where the subtract column component rule is applied to a column which requires "borrowing." For example, consider the sequence of states ##STR4##
where the encircled entities are active and the square designates the goal at that state.
E/F. In turn, the successive pairs of states correspond to the atomic rules: "Go to the top digit in the next column and borrow," "Add the borrowed 10 to the top number in the original column," "Subtract the original column (using basic facts)." The natural domains, respectively, are: "Problems with next column," "All problems in which a borrow has been initiated," "Columns where the top digit(s) are not smaller than the bottom digit(s)."
G. There is an extra-domain attached to the first of these atomic rules. Specifically, this rule is applied only where the "top digit(s) in a column is less than the bottom digit."
At this point, then, associated with the Level II "subtract the column" rule (as illustrated with the second column of the given problem), we have a sequence of subatomic rules, preceded by an extra-domain condition.
H. The next question is whether some consecutive subsequence of these subatomic rules, including the first one, ever generates a state whose active components satisfy the extra-domain condition (i.e., top digit(s) less than the bottom one). Going to the next column and borrowing (the first of the subatomic rules) certainly does not generate such a state, and neither do the first two subrules--or all three.
Once one has borrowed (after the first two subrules have been applied), the top digits (now there are two digits at the top of the column) always represent a number larger than the bottom one. Consequently, the extra-domain condition does not apply. After subtracting the original column (applying all three subrules in turn), we have done the equivalent of the Level II "subtract the column" rule so control moves to the previously defined iteration "While there is a next column."
For these reasons, the extra-domain condition "Top digit(s) less than bottom one" is NOT an iteration. Therefore, it defines a selection.
Moreover, analysis of subtraction in the first column of the problem tells what happens when the complementary extra-domain condition is satisfied (i.e., when the top number is greater than or equal to the bottom one). In this case, one simply subtracts using the basic facts. Hence, the selection is completely defined. If the top number is greater than or equal to the bottom one, we subtract using the basic facts; otherwise, we borrow and then subtract.
Notice that the entire selection construct, including the alternative atomic rules, is contained within (bounded by) the iteration condition ("There is a next column") defined at the previous level of analysis.
It also is important to observe that the iterations and selections identified in an analysis need not be fully defined. In the present case, for example, we were fortunate (or had the clairvoyance) to select a problem that involved both borrow and non-borrow columns. If this had not been the case, then our analysis would not have been complete. We would have known that a selection was involved, and we would have known one of the two alternatives. But we would not have known the other alternative.
In circumstances such as this, one must repeat the above process with new problems--hopefully ones in which the previously unused conditions are satisfied. The results of each new analysis, then, must be combined level by level and component by component with the initial one. The process must be continued with new problems until the underlying procedure is completely defined. In this regard, notice that there always is a finite number of problems that will suffice for this purpose because the number of conditions in any procedure must be finite."
Nothing new is involved in extending the above process to borrowing across O's. This can be accomplished by introducing a selection (within the borrow selection).
Clearly, the goal of structural analysis was to develop an explicit, repeatable and potentially automatable process for analyzing content. Although the context was completely different, these goals clearly are quite analogous to those common in most software engineering methodologies (e.g., Booch, 1994; Rumbaugh, et al., 1991; Yourdon 1989). Structural analysis, however, differs from traditional software engineering methods in several fundamental ways.
First, unlike software engineering, the original goal of structural analysis (e.g., Scandura et al, 1971; Scandura, 1982, 1984a) was to analyze complex, sometimes called ill-defined domains. III-defined domains are problem domains that transcend any given finite set of solution rules. That is, no finite set of rules can be found that is sufficient for solving all problems in the domain. Structural analysis was designed to address this problem. The basic idea was to identify sets of rules and higher order rules that collectively would make it possible to solve qualitatively greater numbers of problems in ill-defined domains than would otherwise be possible.
As described in Scandura (1984a, pp. 23-7), structural analysis of complex domains begins by selecting a representative sample of solvable problems in the domain. Next, a solution rule is derived (e.g., by the above methods) for each type of problem. This results in a set of solution rules that is sufficient for solving problems similar to the sample problems. A key idea in structural analysis is that one can usually find parallels between different solution rules. These parallels typically reflect the fact that the solution rules can be derived via the same higher order rule. Moreover, as indicated by Scandura (1984a, p.23), solution rules correspond to higher order problems, namely problems for which they are solutions.
Structural analysis takes higher order problems as new starting place and the process (of identifying solution rules) is repeated. This time the results are higher order rules which operate on and/or generate other rules. The process of moving to higher and higher levels can continue indefinitely.
Each iteration leads to rules which are simpler individually, but which collectively are more powerful in the sense that they account for qualitatively broader varieties of problems. That is, when used in combination, higher order rules may generate new rules which in turn make it possible to make it possible to generate new solution rules and/or problems. Structural analysis also takes into account that solution rules derived in this way may include previously identified rules. Hence, a final step in structural analysis is to eliminate redundant rules. A number of applications of structural analysis are summarized in Scandura (1982).
A second major difference between software engineering and structural analysis is that data and process in structural analysis are refined in parallel (from the top down). In structured analysis, for example, all of the required inputs and outputs are assumed from the beginning. In structural analysis, data abstractions are defined only as needed in process refinement.
A major limitation of structural analysis as regards software engineering is its informality. Ambiguities, omissions, and lack of scalability to complex systems, make it unsuitable as a foundation for automation and even less for ensuring the correctness of complex software systems. Indeed, the possibility of ensuring correctness of an analysis, whether internal or external, was not seriously considered.
What is needed is a repeatable, formally verifiable and intuitive process that is easy to use. Specifically, this process must provide human designers with automated support making it easy to implement arbitrarily large, complex software systems that are both internally consistent and logically correct (that are consistent with specifications).
Domain Analysis
Domain analysis (e.g., Krut et al, 1996) has become a new and active area of research in recent years. Like structural analysis, domain analysis is concerned with ill-defined domains (e.g., word processing, software engineering [tools]). Most software engineers, however, are not familiar with prior work in structural analysis (understandably using such terms as analysis, design and application). Consequently, whereas structural analysis would seek parallels between different (lower order) applications (attempting to represent these parallels in terms of higher order designs), domain analysis has taken a different tact. Thus, instead of seeking ways to identify higher and lower order components for constructing applications from more basic components, domain analysis looks for similarities and differences between alternative applications. Although such information can be useful in designing specific applications in a given domain, domain analysis does not provide the information necessary to help automate the construction of such applications.
Control Mechanisms
A final line of prior research is relevant to the present disclosure. This pertains to the way in which given sets of rules are used in solving problems (e.g., see Winston, 1977, pp. 129-156). Given a problem together with a set of rules (and higher order rules), the question is how those rules are to be used in attempting to solve the problem. A variety of mechanisms have been proposed for searching and controlling interactions among available rules (or what are commonly called productions). Various combinations of forward and backward chaining have been most common. Forward chaining involves selecting rules in order beginning with the problem given. Backward chaining begins by selecting a rule that would solve the problem given that rule's input.
Two basic approaches have been widely used. An approach called means-ends analysis bases the selection and use of rules on computed differences between given and goal states. The success of this approach depends on finding a useful and universally applicable way to compute differences.
Another approach is based on sets of independent productions, each consisting of an operation and a set of conditions defining its domain of applicability. Rather than relying on differences between goals and what is given, production systems allow more flexible control. Individual productions are triggered by currently available inputs. Productions are selected by matching what is available with production domains. The order in which productions are listed can be important. When more than one production matches a given situation, conflicts can be resolved in any number of ways: first production found, most complete match, most recently used, etc. Productions and problem categories can also be partitioned into classes.
Productions systems are fully modular. New productions may be added as desired. Given productions can even control interactions among other productions. Within the artificial intelligence community, productions are typically identified by a process called "knowledge engineering". This is a largely informal process whereby a domain expert identifies and represents individual items of knowledge as productions.
Structural (cognitive task) analysis (e.g., Scandura et al, 1971, Scandura, 1982) represents a more systematic approach to the same problem. Two major characteristics distinguish structural analysis: (a) operations identified via structural analysis may be refined into their constituents and (b) higher order rules which operate on and/or generate other rules are identified in a systematic manner. The former supports the inclusion of productions with non-elementary operations, which we call solution rules. The explicit introduction of higher as well as lower order rules in the latter provides an explicit basis for predicting coverage of the initial problem domain. Lower order rules can only be combined and/or otherwise modified via explicitly identified higher order rules. The order in which rules are listed plays no essential role.
The Structural Learning Theory (e.g., Scandura, 1971, 1973, 1977) builds on these two characteristics of structural analysis. This theory includes corresponding mechanisms for: (a) assessing the knowledge state of individual human beings relative to a set of rules and (b) controlling interactions between rules. Specifically, in the latter case, a generalized "goal switching" mechanism was proposed to control interactions between higher and lower order rules: If an available rules applies, use it. Otherwise, control automatically switches to a higher order goal of deriving one. Higher order rules are applied in this case, thereby generating new rules that apply to the original situation. This mechanism was later modified (Scandura, 1993) so a rule is applied only where exactly one rule applies (no more and no fewer). Otherwise, higher order goals are invoked. This modification provides an explicit base for rule selection in which more than one rule can be used.
The goal switching mechanism appears to be straightforward and potentially applicable to all problem domains. Moreover, strong empirical support suggesting its universal availability to human beings has been found in a variety of research studies (e.g., Scandura, 1977; Scandura & Scandura, 1980). Nonetheless, this mechanism has never been detailed with the precision necessary for implementation in a devise with memory in a completely general manner. Goal switching control and higher order rules, for example, are intrinsically intertwined in the computer simulation reported by Wulfeck and Scandura (in Chapter 14 of Scandura, 1977). In the original goal switching control mechanism, higher order goals are defined as sets of rules for solving lower order problems (see Scandura, 1973, p.293). Because higher order goals and higher order rules are defined in the same way, it is impossible to construct an independent test to determine whether a given higher order rule satisfies the higher order goal.